﻿namespace AdvancedTraining.Lesson42;

/// <summary>
/// 最佳开会地点问题
/// </summary>
/// <remarks>
/// https://www.cnblogs.com/singroupyu/p/15091107.html
/// LeetCode 0296
///
/// 问题描述：
/// 有一个网格，1代表人，0代表障碍物，空位代表空地。
/// 选择一个空地，让所有在网格上的人到这个空地的总移动距离最小。
/// 如果有多个最佳地点，返回其中任意一个
///
/// 算法思路：
/// 这是一个经典的数学优化问题。关键观察：
/// 1. 最佳地点一定是某个人的位置
/// 2. 总距离可以分解为每个人到该地点的曼哈顿距离之和
/// 3. 曼哈顿距离 = |x1 - x2| + |y1 - y2|
///
/// 使用中位数原理：
/// - 在一维中，使所有人到某点的距离最小，该点就是中位数
/// - 在二维中，最佳地点的x坐标是所有人的x坐标的中位数
/// - 最佳地点的y坐标是所有人的y坐标的中位数
///
/// 实现步骤：
/// 1. 统计每行和每列的人数
/// 2. 找到最佳的行位置（中位数）
/// 3. 找到最佳的列位置（中位数）
/// 4. 计算总距离
///
/// 时间复杂度：O(NM)，其中N是行数，M是列数
/// 空间复杂度：O(N+M)
/// </remarks>
public class BestMeetingPoint // leetcode_0296
{
    /// <summary>
    /// 计算最佳开会地点的最小总距离
    /// </summary>
    /// <param name="grid">网格，1代表人，0代表障碍物，空位代表空地</param>
    /// <returns>最小总距离</returns>
    public static int MinTotalDistance(int[][] grid)
    {
        if (grid == null || grid.Length == 0 || grid[0].Length == 0)
            return 0;

        var n = grid.Length;
        var m = grid[0].Length;
        var iOnes = new int[n];
        var jOnes = new int[m];

        // 统计每行和每列的人数
        for (var i = 0; i < n; i++)
        {
            for (var j = 0; j < m; j++)
            {
                if (grid[i][j] == 1)
                {
                    iOnes[i]++;
                    jOnes[j]++;
                }
            }
        }

        // 找到最佳的行位置（中位数）
        var total = 0;
        var i1 = 0;
        var i2 = n - 1;
        var iRest = 0;
        var jRest = 0;
        while (i1 < i2)
        {
            if (iOnes[i1] + iRest <= iOnes[i2] + jRest)
            {
                total += iOnes[i1] + iRest;
                iRest += iOnes[i1++];
            }
            else
            {
                total += iOnes[i2] + jRest;
                jRest += iOnes[i2--];
            }
        }

        // 找到最佳的列位置（中位数）
        i1 = 0;
        i2 = m - 1;
        iRest = 0;
        jRest = 0;
        while (i1 < i2)
        {
            if (jOnes[i1] + iRest <= jOnes[i2] + jRest)
            {
                total += jOnes[i1] + iRest;
                iRest += jOnes[i1++];
            }
            else
            {
                total += jOnes[i2] + jRest;
                jRest += jOnes[i2--];
            }
        }

        return total;
    }

    /// <summary>
    /// 运行测试用例
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("=== BestMeetingPoint 测试 ===");

        // 测试用例1：LeetCode官方示例1
        var grid1 = new int[][]
        {
            new[] { 1, 0, 0, 0, 1 },
            new[] { 0, 0, 0, 0, 0 },
            new[] { 0, 0, 1, 0, 0 },
            new[] { 0, 0, 0, 0, 0 }
        };
        Console.WriteLine("测试1 - LeetCode官方示例1:");
        Console.WriteLine($"输入网格: 4x5, 2个人");
        Console.WriteLine($"结果: {MinTotalDistance(grid1)} (期望: 6)");
        Console.WriteLine();

        // 测试用例2：简单情况 - 单个人
        var grid2 = new int[][]
        {
            new[] { 1, 0, 0 },
            new[] { 0, 0, 0 }
        };
        Console.WriteLine("测试2 - 单个人:");
        Console.WriteLine($"输入网格: 2x3, 1个人");
        Console.WriteLine($"结果: {MinTotalDistance(grid2)} (期望: 0)");
        Console.WriteLine();

        // 测试用例3：多个人在边界
        var grid3 = new int[][]
        {
            new[] { 1, 0, 0 },
            new[] { 0, 0, 0 },
            new[] { 0, 0, 1 }
        };
        Console.WriteLine("测试3 - 多个人在边界:");
        Console.WriteLine($"输入网格: 3x3, 3个人");
        Console.WriteLine($"结果: {MinTotalDistance(grid3)} (期望: 4)");
        Console.WriteLine();

        // 测试用例4：空网格
        var grid4 = new int[][]
        {
            new[] { 0, 0, 0 },
            new[] { 0, 0, 0 },
            new[] { 0, 0, 0 }
        };
        Console.WriteLine("测试4 - 空网格:");
        Console.WriteLine($"输入网格: 3x3, 0个人");
        Console.WriteLine($"结果: {MinTotalDistance(grid4)} (期望: 0)");
        Console.WriteLine();

        // 测试用例5：复杂分布
        var grid5 = new int[][]
        {
            new[] { 1, 0, 0, 0, 1 },
            new[] { 0, 1, 1, 0, 0 },
            new[] { 0, 0, 1, 1, 0 },
            new[] { 0, 0, 0, 0, 0 },
            new[] { 0, 0, 0, 0, 1 }
        };
        Console.WriteLine("测试5 - 复杂分布:");
        Console.WriteLine($"输入网格: 5x5, 6个人");
        Console.WriteLine($"结果: {MinTotalDistance(grid5)} (期望: 15)");
        Console.WriteLine();

        // 测试用例6：所有人都在同一位置
        var grid6 = new int[][]
        {
            new[] { 1, 1, 1 },
            new[] { 0, 0, 0 },
            new[] { 0, 0, 0 }
        };
        Console.WriteLine("测试6 - 所有人都在同一位置:");
        Console.WriteLine($"输入网格: 3x3, 3个人在同一位置");
        Console.WriteLine($"结果: {MinTotalDistance(grid6)} (期望: 2)");
        Console.WriteLine();

        // 测试用例7：大网格测试
        var grid7 = new int[5][];
        var random = new Random();
        for (var i = 0; i < 5; i++)
        {
            grid7[i] = new int[5];
            for (var j = 0; j < 5; j++)
            {
                grid7[i][j] = random.Next(2) == 1 ? 1 : 0;
            }
        }
        Console.WriteLine("测试7 - 随机网格:");
        Console.WriteLine($"输入网格: 5x5, 随机分布");
        Console.WriteLine($"结果: {MinTotalDistance(grid7)} (预期: 非负数)");
        Console.WriteLine();

        Console.WriteLine("=== 算法说明 ===");
        Console.WriteLine("算法思路：中位数原理");
        Console.WriteLine("- 最佳地点的x坐标是所有1的x坐标的中位数");
        Console.WriteLine("- 最佳地点的y坐标是所有1的y坐标的中位数");
        Console.WriteLine("- 总距离 = 每个人到该地点的曼哈顿距离之和");
        Console.WriteLine("- 时间复杂度：O(N*M)，空间复杂度：O(N+M)");
    }
}